|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Algorithmic aspects of intersection-defined graph classes
Jedličková, Nikola ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
Geometrically representable graphs are extensively studied area of research in contempo- rary literature due to their structural characterizations and efficient algorithms. The most frequently studied class of such graphs is the class of interval graphs. In this thesis we focus on two problems, generalizing the problem of recognition, for classes related to interval graphs. In the first part, we are concerned with adjusted interval graphs. This class has been studied as the right digraph analogue of interval graphs. For interval graphs, there are polynomial algorithms to extend a partial representation by given intervals into a full interval representation. We will introduce a similar problem - the partial ordering extension - and we will provide a polynomial algorithm to extend a partial ordering of adjusted interval digraphs. In the second part, we show two NP-completeness results regarding the simultaneous representation problem, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some k graphs can be represented so that every vertex is represented by the same object in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when k is a part of the input and graphs...
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
guest ::
